/*************************************************************************
	> File Name: oj-260.c
	> Author: Wang Bo
	> Mail: 1276106221@qq.com
	> Created Time: 2020年11月14日 星期六 19时30分11秒
 ************************************************************************/
#include <stdio.h>
#include <string.h>

int to_10[128], to_64[128];
char num[1005], ans[1005];

void init() {
    //快速转换数组
    int t = 0;
    for (int i = '0'; i <= '9'; ++i) {
        to_10[i] = t;
        to_64[t] = i;
        t++;
    }
    for (int i = 'A'; i <= 'Z'; ++i) {
        to_10[i] = t;
        to_64[t] = i;
        t++;
    }
    for (int i = 'a'; i <= 'z'; ++i) {
        to_10[i] = t;
        to_64[t] = i;
        t++;
    }
}

int main() {
    init();
    int a, b;
    scanf("%d%d%s", &a, &b, num);
    printf("%d %s\n%d ", a, num, b);
    int len = strlen(num), t = strlen(num), anslen;
    for (int i = 0; t; ++i) {
        //外层循环存答案
        int k = 0;
        for  (int j = len - t; j < len; ++j) {
            //内层循环同余定理求余数
            k = k * a + to_10[num[j]];
            //商存到原字符串中
            num[j] = to_64[k / b];
            k %= b;
        }
        ans[i] = to_64[k];
        while (t > 0 && num[len - t] == '0') {
            t--;
        }
        anslen = i;
    }
    for (int i = anslen; i >= 0; --i) {
        printf("%c", ans[i]);
    }
    return 0;
}

